// A simple tokenizer for MIPS, written in C, for UW's CS 241
// Written by Aaron Voelker, released under the GNU General Public License v3

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

#define STATES 20
#define MAXTOKEN 10240
#define ERR -1

typedef struct tokenList_ {
    int kind, value;
    char *lexeme;
    struct tokenList_ *next;
} tokenList;

int transitions[STATES][256]; // transitions[i][j] gives the state after reading character j on state i

enum {ID,LABEL,DOTWORD,INT,HEXINT,REGISTER,COMMA,LPAREN,RPAREN,WHITESPACE,ZERO,START,DOLLAR,MINUS,ZEROX,DOT,DOTW,DOTWO,DOTWOR,COMMENT} states;
const int stateToKind[STATES] = {ID,LABEL,DOTWORD,INT,HEXINT,REGISTER,COMMA,LPAREN,RPAREN,WHITESPACE,INT,ERR,ERR,ERR,ERR,ERR,ERR,ERR,ERR,ERR};
const char *kindToString[STATES] = {"ID","LABEL","DOTWORD","INT","HEXINT","REGISTER","COMMA","LPAREN","RPAREN","WHITESPACE"};

const char *alphanumerals = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
const char *alphabet =      "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
const char *oneToNine =     "123456789";
const char *digits =        "0123456789";
const char *hexDigits =     "0123456789abcdefABCDEF";
const char *whitespace =    "\r\n\t ";

void newLexer() { // Builds transition table to initiate lexer
    int i;
    const char *c;
    memset(transitions, ERR, sizeof(transitions));
    for(c=alphabet; *c; c++)      transitions[START][*c]    = ID;       // identifiers
    for(c=alphanumerals; *c; c++) transitions[ID][*c]       = ID;
    transitions[ID][':']          = LABEL;
    for(c=oneToNine; *c; c++)     transitions[START][*c]    = INT;      // values
    for(c=digits; *c; c++)        transitions[INT][*c]      = INT;
    transitions[START]['-']       = MINUS;
    for(c=digits; *c; c++)        transitions[MINUS][*c]    = INT;
    transitions[START]['0']       = ZERO;
    for(c=digits; *c; c++)        transitions[ZERO][*c]     = INT;
    transitions[ZERO]['x']        = ZEROX;
    for(c=hexDigits; *c; c++)     transitions[ZEROX][*c]    = HEXINT;
    for(c=hexDigits; *c; c++)     transitions[HEXINT][*c]   = HEXINT;
    transitions[START]['$']       = DOLLAR;                             // registers
    for(c=digits; *c; c++)        transitions[DOLLAR][*c]   = REGISTER;
    for(c=digits; *c; c++)        transitions[REGISTER][*c] = REGISTER;
    transitions[START][',']       = COMMA;                              // single character tokens
    transitions[START]['(']       = LPAREN;
    transitions[START][')']       = RPAREN;
    transitions[START]['.']       = DOT;                                // .word directive
    transitions[DOT]['w']         = DOTW;
    transitions[DOTW]['o']        = DOTWO;
    transitions[DOTWO]['r']       = DOTWOR;
    transitions[DOTWOR]['d']      = DOTWORD;
    transitions[START][';']       = COMMENT;                            // comments & whitespace
    for(i=0; i<256; i++)          transitions[COMMENT][i]  = COMMENT;
    transitions[COMMENT]['\r']    = WHITESPACE;
    transitions[COMMENT]['\n']    = WHITESPACE;
    for(c=whitespace; *c; c++)    transitions[START][*c]   = WHITESPACE;
}

void freeTokenList(tokenList *list) {
    if(list) {
        freeTokenList(list->next);
        free(list->lexeme);
        free(list);
    }
}

tokenList *newToken(int kind, const char *lexeme) {
    int value=0;
    if(kind == INT || kind == HEXINT || kind == REGISTER) { // Determine value
        if     (lexeme[0]=='-') value = strtol(lexeme, NULL, 10);
        else if(lexeme[0]=='$') value = strtol(&lexeme[1], NULL, 10);
        else                    value = strtoul(lexeme, NULL, kind == HEXINT ? 16 : 10);
        if(errno == ERANGE) return NULL;                // Out of range
        if(kind == REGISTER && value > 31) return NULL; // Out of range
    }
    tokenList *t = (tokenList *)malloc(sizeof(tokenList));
    if(t == NULL) return NULL; // Memory error
    t->kind = kind, t->value = value, t->next = NULL;
    t->lexeme = (char *)malloc(sizeof(char)*(strlen(lexeme)+1));
    if(t->lexeme == NULL) return free(t), NULL; // Memory error
    strcpy(t->lexeme, lexeme);
    return t;
}

char lexer_token[MAXTOKEN+1];
tokenList *scan(const char *input) { // O(N) Simplified Maximal Munch Algorithm
    int i=0, state, length;
    tokenList *head = NULL, **tail = &head;
    while(input[i]) {
        state = START, length = 0;
        while(transitions[state][input[i]] != ERR && length<MAXTOKEN) { // DFA until error
            lexer_token[length++] = input[i];
            state = transitions[state][input[i++]];
        }
        lexer_token[length] = '\0';
        if(stateToKind[state] == ERR) { // Not a final state
            fprintf(stderr, "ERROR stray character (%c) after (%.*s)\n", input[i], i, input);
            return freeTokenList(head), NULL;
        }
        if(state != WHITESPACE) {
            if((*tail = newToken(stateToKind[state], lexer_token)) == NULL) {
                fprintf(stderr, "ERROR out of range (%s) or insufficient memory\n", lexer_token);
                return freeTokenList(head), NULL;
            }
            tail = &((*tail)->next);
        }
    }
    return head;
}

int main() { // Sample program demonstrating the use of the lexer
    char line[256];
    newLexer();
    tokenList *list, *head;
    while(fgets(line, sizeof(line), stdin)) {
        head = list = scan(line);
        while(list) {
            fprintf(stderr, "  Token: %s {%s}\n", kindToString[list->kind], list->lexeme);
            list = list->next;
        }
        freeTokenList(head);
    }
    return 0;
}
